package tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Created with Intellij IDEA.
 * Description;
 * User:墨琦
 * Data:2023-04-18
 * Time:18:46
 */
public class BinaryTree {
   static class Tree  {
       Tree left;
       Tree right;
       int val;
       Tree(){}
       Tree(int num)
       {
           this.val=num;
       }
   }
     public void creat(Tree root)
     {
         Tree B=new Tree(1);
         Tree C=new Tree(2);
         Tree D=new Tree(7);
         Tree E=new Tree(6);
         Tree F=new Tree(8);
         Tree G=new Tree(9);
         root.left=B;
         root.right=C;
         B.left=D;
         B.right=E;
         C.left=F;
         C.right=G;
     }
     public int getTreeRoot(Tree root)
     {
         if(root == null)
         {
             return 0;
         }
         int lefth=getTreeRoot(root.left);
         int righth=getTreeRoot(root.right);
         return (Math.max(lefth, righth))+1;
     }
    public Tree find(Tree root,int vals)
    {
        Tree code;
        if(root==null)
        {
            return null;
        }
        if(root.val==vals)
        {
            return root;
        }

        code=find(root.left,vals);
        if(code==null)
        {
            code=find(root.right,vals);
        }
        return code;
    }
    public Tree reversal(Tree root)
    {
        if(root==null)
        {
            return null;
        }
        Tree A=root.left;
        root.left=root.right;
        root.right=A;
        reversal(root.left);
        reversal(root.right);
        return root;
    }
    public boolean image(Tree root)
    {
        if(root==null)
        {
            return true;
        }
        else  return isSymmetricChild(root.left,root.right);
    }
    public boolean isSymmetricChild(Tree lefth,Tree righth)
    {
        if(lefth==null&&righth==null)
        {
            return true;
        }
        if(lefth==null||righth==null||lefth.val!= righth.val)
        {
            return false;
        }
        return isSymmetricChild(lefth.left,righth.right)&&isSymmetricChild(lefth.right,righth.left);
    }
    public void show(Tree root)
    {
        if(root==null)
        {
            return ;
        }
        System.out.println(root.val+" ");
        show(root.left);
        show(root.right);
    }
    //层序遍历
    public void levelOrder(Tree root)
    {
        Queue<Tree> fw=new LinkedList<>();
        if(root!=null)
        {
            fw.add(root);
        }
        while(!fw.isEmpty())
        {
            Tree fw1=fw.poll();
            System.out.print(fw1.val+" ");
            if(fw1.left!=null)
            {
                fw.add(fw1.left);
            }
            if(fw1.right!=null)
            {
                fw.add(fw1.right);
            }
        }
    }

    //层序遍历
    public List<List<Integer>>  levelOrder2(Tree root)
    {
        List<List<Integer>> ret=new ArrayList<>();
        if(root==null)
        {
            return ret;
        }
        Queue<Tree> fw=new LinkedList<>();
        fw.offer(root);
       while(!fw.isEmpty())
       {
           List<Integer> list=new ArrayList<>();
           int size=fw.size();
           while(size>0)
           {
               Tree kk=fw.poll();
               list.add(kk.val);
               if(kk.left!=null)
               {
                   fw.offer(kk.left);
               }
               if(kk.right!=null)
               {
                   fw.offer(kk.right);
               }
               size--;
           }
           ret.add(list);
       }
       return ret;
    }
    //判断是否为完全二叉树
    public boolean isCompeteTree(Tree root)
    {
        Queue<Tree> fw=new LinkedList<>();
        if(root!=null)
        {
            fw.offer(root);
        }
        while(!fw.isEmpty())
        {
            Tree code=fw.poll();
            if(code!=null)
            {
                fw.offer(code.left);
                fw.offer(code.right);
            }
            else break;
        }
        while(!fw.isEmpty())
        {
            if(fw.poll()!=null)
            {
                return false;
            }
        }
        return true;
  }
  //根据前序和中序，创建二叉树
  public int pret=0;
  public Tree CreatTree(int[] array1,int[] array2)
  {
      return CreatTree2(array1,array2,0, array2.length-1);
  }
  public Tree CreatTree2(int[] array1,int[] array2,int cin,int cur)
  {
      if(cin>cur)
      {
          return null;
      }
      Tree root=new Tree(array1[pret]);
      int ret=find(array2,cin,cur,array1[pret]);
      pret++;
      root.left=CreatTree2(array1,array2,cin,ret-1);
      root.right=CreatTree2(array1,array2,ret+1,cur);
      return root;
  }
  public int find(int[] array2,int cin,int cur,int key)
  {
      while(cin<=cur)
      {
          if(array2[cin]==key)
              return cin;
         cin++;
      }
      return -1;
  }
}

